class Solution
{
public:
    vector<int> rearrangeBarcodes(vector<int> &barcodes)
    {
        unordered_map<int, int> m;
        for (auto &ch : barcodes)
        {
            m[ch]++;
        }
        int maxcount = 0;
        int num;
        for (auto &ch : m)
        {
            if (ch.second > maxcount)
            {
                maxcount = ch.second;
                num = ch.first;
            }
        }
        int i = 0;
        int tem = m[num];
        while (tem--)
        {
            barcodes[i] = num;
            i += 2;
        }
        m.erase(num);
        for (auto &ch : m)
        {

            int count = ch.second;
            while (count--)
            {
                if (i >= barcodes.size())
                    i = 1;
                barcodes[i] = ch.first;
                i += 2;
            }
        }
        return barcodes;
    }
};